package com.lfg.leetcode.leetcode200;

public class WordDictionary {


    Node root;

    public WordDictionary() {
        root = new Node();
    }

    public static void main(String[] args) {
        WordDictionary dictionary = new WordDictionary();
        dictionary.addWord("bd");
//        dictionary.addWord("dad");
//        dictionary.addWord("mad");
//        System.out.println(dictionary.search("pad"));// -> false
//        System.out.println(dictionary.search("bad"));// -> true
//        System.out.println(dictionary.search(".ad"));//-> true
        System.out.println(dictionary.search("."));// -> true
    }

    public void addWord(String word) {
        Node e = root;
        for (int i = 0; i < word.length(); i++) {
            int pos = word.charAt(i) - 'a';
            if (pos < 0) {
                pos = 26;
            }
            Node child = e.children[pos];
            if (null == child) {
                child = new Node();
                e.children[pos] = child;
                e.childrenLen++;
                child.val = word.charAt(i);
            }
            e = child;
        }
        e.cnt++;
    }

    public boolean search(String word) {
        if ('.' != word.charAt(0)) {
            int pos = word.charAt(0) - 'a';
            Node child = root.children[pos];
            return search(child, word, 1);
        }

        for (Node node : root.children) {
            if (search(node, word, 1)) {
                return true;
            }
        }
        return false;
    }

    public boolean search(Node root, String word, int index) {
        Node e = root;
        if (null == root) {
            return false;
        }
        if (index >= word.length() && e.cnt > 0) {
            return true;
        }
        if (index >= word.length()) {
            return false;
        }

        for (int i = index; i < word.length(); i++) {
            if (word.charAt(i) == '.' || null != e.children[26]) {
                for (Node node : e.children) {
                    if (search(node, word, i + 1)) {
                        return true;
                    }
                }
                return false;
            }
            int pos = word.charAt(i) - 'a';
            e = e.children[pos];
            if (null == e) {
                return false;
            }
        }
        return e.cnt > 0;
    }

    class Node {
        char val;
        Node children[] = new Node[27];
        int childrenLen;
        int cnt;
    }
}
